Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 103/115

Q: Which scheme uses a randomization approach?
A. hashing by division
B. hashing by multiplication
C. universal hashing
D. open addressing
Solution: Universal hashing scheme uses a randomization approach whereas hashing by division and hashing by multiplication are heuristic in nature.
Q: Which hash function satisfies the condition of simple uniform hashing?
A. h(k) = lowerbound(km)
B. h(k)= upperbound(mk)
C. h(k)= lowerbound(k)
D. h(k)= upperbound(k)
Solution: If the keys are known to be random real numbers k independently and uniformly distributed in the range 0<=k<=1, the hash function which satisfies the condition of simple uniform hashing is
h(k)= lowerbound(km).
Q: Interpret the given character string as an integer expressed in suitable radix notation.

Character string = pt
A. 14963
B. 14392
C. 12784
D. 14452
Solution: The given character string can be interpreted as (112,116) (Ascii values) then expressed as a radix-128 integer, hence the value is 112*128 + 116 = 14452.
Q: What is the hash function used in the division method?
A. h(k) = k/m
B. h(k) = k mod m
C. h(k) = m/k
D. h(k) = m mod k
Solution: In division method for creating hash functions, k keys are mapped into one of m slots by taking the reminder of k divided by m.
Q: What can be the value of m in the division method?
A. Any prime number
B. Any even number
C. 2p – 1
D. 2p
Solution: A prime number not too close to an exact power of 2 is often a good choice for m since it reduces the number of collisions which are likely to occur.
Q: Which scheme provides good performance?
A. open addressing
B. universal hashing
C. hashing by division
D. hashing by multiplication
Solution: Universal hashing scheme provides better performance than other schemes because it uses a unique randomisation approach.
Q: Using division method, in a given hash table of size 157, the key of value 172 be placed at position ____
A. 19
B. 72
C. 15
D. 17
Solution: The key 172 can be placed at position 15 by using the formula
H(k) = k mod m
H(k) = 172 mod 157
H(k) = 15.
Q: How many steps are involved in creating a hash function using a multiplication method?
A. 1
B. 4
C. 3
D. 2
Solution: In multiplication method 2 steps are involved. First multiplying the key value by a constant. Then multiplying this value by m.
Q: What is the hash function used in multiplication method?
A. h(k) = floor( m(kA mod 1))
B. h(k) = ceil( m(kA mod 1))
C. h(k) = floor(kA mod m)
D. h(k) = ceil( kA mod m)
Solution: The hash function can be computed by multiplying m with the fractional part of kA (kA mod 1) and then computing the floor value of the result.
Q: What is the advantage of the multiplication method?
A. only 2 steps are involved
B. using constant
C. value of m not critical
D. simple multiplication
Solution: The value of m can be simply in powers of 2 since we can easily implement the function in most computers. m=2p where p is an integer.

You Have Score    /10